#include <stdio.h>
#include <string.h>

#include "string_rld.h"

string merge_sort(string pResult, const string pString){

    if (strlen(pString) <= 1)
        strcpy (pResult, pString);
    else
    {
        // Merge del segmento izquierdo.
        char left [strlen(pString) / 2 + 1];                  
        stringNCopy(left, pString, strlen(pString)/2);        
        
        char left_sorted [strlen(pString) / 2 + 1];           
        initString(left_sorted, strlen(pString) / 2 );
        
        merge_sort(left_sorted, left);

        // Merge del segmento derecho.
        char right [strlen(pString) / 2 + 1];
        initString(right, strlen(pString) / 2);
        
        strcpy (right, pString + (strlen(pString)/2));
        
        char right_sorted [strlen(pString) / 2 + 1];
        initString(right_sorted, strlen(pString) / 2);

        merge_sort(right_sorted, right);

        //Merge de ambos segmentos ordenados.
        merge (pResult, left_sorted, right_sorted);
        
    }
    
    return pResult;    
    
} // merge_sort

string merge (string pStringMerged, string left, string right){
    
    while ( strlen(left) > 0 || strlen(right) > 0 )
    {
        if (strlen(left) > 0 && strlen(right) > 0)
        {
            if ( left[0] <= right[0] )
            {
                append(pStringMerged, left[0]);
                left ++;
            }
            else
            {
                append(pStringMerged, right[0]);
                right ++;
            }
        }
        else if ( strlen(left) > 0 )
        {
            append(pStringMerged, left[0]);
            left ++;
        }
        else if ( strlen(right) > 0 )
        {
            append(pStringMerged, right[0]);
            right ++;
        }
        
    }

    return pStringMerged;
  
} // merge

